import functools


#  记忆化搜索
# class Solution(object):
#     def countSubstrings(self, s):
#         """
#         :type s: str
#         :rtype: int
#         """
#         n = len(s)
#
#         @functools.cache
#         def judge(i, j):
#             if j == i:
#                 return True
#             else:
#                 if j - i == 1:
#                     return s[i] == s[j]
#                 else:
#                     return judge(i + 1, j - 1) and (s[i] == s[j])
#
#         @functools.cache
#         def count(k):
#             if k == 0:
#                 return 1
#             else:
#                 value = count(k - 1)
#                 for i in range(k + 1):
#                     value += judge(i, k)
#                 return value
#
#         return count(n - 1)

# manache算法
class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """

        def expand(i, j):
            while i >= 0 and j < n and s[i] == s[j]:
                i -= 1
                j += 1
            return (j - i - 2) // 2

        s = '#' + '#'.join(s) + '#'
        n = len(s)
        p = [0] * n
        p[1] = 1
        right_max = 2
        center = 1
        for i in range(2, n):
            if i >> right_max:
                p[i] = expand(i, i)
                right_max = i + p[i]
                center = i
            else:
                morrior_i = 2 * center - i
                r = min(right_max - i, p[morrior_i])
                R = expand(i - r, i + r)
                p[i] = R
                if R > r:
                    right_max = i + R
                    center = i
        ans = 0
        for item in p:
            ans += (item + 1) // 2
        return ans

data = Solution()
s = "dnncbwoneinoplypwgbwktmvkoimcooyiwirgbxlcttgteqthcvyoueyftiwgwwxvxvg"
print(data.countSubstrings(s))
